1. Field of the Disclosure
This disclosure relates generally to dynamic-sized shared data structures, and more particularly to systems and methods for exploiting hardware transactions in managing memory for such data structures.
2. Description of the Related Art
The multi-core revolution currently in progress is making it increasingly important for applications to exploit concurrent execution in order to take advantage of advances in technology. For example, it may be possible to increase parallelism by allowing multiple threads to execute a critical section at one time if the executions do not rely on overlapping memory locations. Shared-memory systems allow multiple threads to access and operate on the same memory locations, e.g., locations within concurrent dynamic-sized data structures.
Dynamic memory management is a significant source of complexity in the design and implementation of practical concurrent data structures. The Java™ concurrency libraries provide a number of lock-free data structures that have no counterparts in C++. A key obstacle to porting them to C++ is that Java is garbage-collected, while C++ requires explicit memory management, which can be very difficult to implement correctly for concurrent dynamic-sized data structures.
Transactional memory (TM) is a mechanism that can be leveraged to enable concurrent and correct execution of a critical section by multiple threads. Transactional memory allows a thread to execute a block of instructions either completely and atomically or not at all. For example, transactional memory allows programmers to use transactional or atomic blocks, which may be considered sequential code blocks that should be executed atomically. In other words, executions of atomic blocks by different threads do not appear to be interleaved. To execute an atomic block, the underlying system may begin a transaction, execute the atomic block's memory accesses using that transaction, and then may try to commit the transaction. If the transaction commits successfully, the atomic block's execution seems to take effect atomically at the transaction's commit point. If it fails, the execution does not seem to take effect at all and the atomic block might be retried using a new transaction. It is the responsibility of the TM implementation to guarantee the atomicity of operations executed by transactions. The transactional memory paradigm can significantly simplify the design of concurrent programs. In general, transactional memory can be implemented in hardware (HTM), in software (STM), or as a hybrid transactional memory system (HyTM).